#include <vector>

// 时间复杂度为O(N*logN)
// 空间复杂度为O(N)
// 稳定的排序
void _MergeSort(std::vector<int> &nums, int begin, int end, std::vector<int> &tmp)
{
    if (begin >= end)
        return;
    int mid = (end - begin) / 2 + begin;

    _MergeSort(nums, begin, mid, tmp);
    _MergeSort(nums, mid + 1, end, tmp);

    // 归并 取小的尾插
    // [begin, mid] [mid+1, end]
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;

    int i = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (nums[begin1] <= nums[begin2])
        {
            tmp[i++] = nums[begin1++];
        }
        else
        {
            tmp[i++] = nums[begin2++];
        }
    }

    while (begin1 <= end1)
    {
        tmp[i++] = nums[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = nums[begin2++];
    }

    std::copy(tmp.begin() + begin, tmp.begin() + i, nums.begin() + begin);
}

void MergeSort(std::vector<int> &nums)
{
    int n = nums.size();
    std::vector<int> tmp(n);
    _MergeSort(nums, 0, n - 1, tmp);
}

void MergeSortNonR(std::vector<int> &nums)
{
    int n = nums.size();
    std::vector<int> tmp(n);

    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            // 第一组越界
            if (end1 >= n)
                break;
            // 第二组全部越界
            if (begin2 >= n)
                break;
            // 第二组部分越界
            if (end2 >= n)
                end2 = n - 1;

            int j = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (nums[begin1] <= nums[begin2])
                {
                    tmp[j++] = nums[begin1++];
                }
                else
                {
                    tmp[j++] = nums[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[j++] = nums[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[j++] = nums[begin2++];
            }

            std::copy(tmp.begin() + i, tmp.begin() + j, nums.begin() + i);
        }

        gap *= 2;
    }
}